class Solution {
public:
    bool res = false;
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
    void dfs(int x, int y, int pos, vector<vector<bool>>& vis,
             vector<vector<char>>& board, const string& word) {
        if (pos == word.size()) {
            res = true;
            return;
        }
        int sx = board.size();
        int sy = board[0].size();
        for (int i = 0; i < 4; i++) {
            int x1 = x + dx[i];
            int y1 = y + dy[i];
            if (x1 >= 0 && x1 < sx && y1 >= 0 && y1 < sy && !vis[x1][y1] &&
                board[x1][y1] == word[pos]) {
                vis[x1][y1] = true;
                dfs(x1, y1, pos + 1, vis, board, word);
                vis[x1][y1] = false;
            }
        }
    }
    bool exist(vector<vector<char>>& board, string word) {
        int sx = board.size();
        int sy = board[0].size();
        for (int i = 0; i < sx; i++) {
            for (int j = 0; j < sy; j++) {
                if (board[i][j] == word[0]) {
                    vector<vector<bool>> vis(sx, vector<bool>(sy, false));
                    vis[i][j] = true;
                    dfs(i, j, 1, vis, board, word);
                    if (res)
                        return true;
                }
            }
        }
        return false;
    }
};